package _18_剑指OfferII;

import java.util.*;

public class _119_剑指OfferII最长连续序列 {

    public static void main(String[] args) {


        int[] ins = {100,4,200,1,3,2};
        _119_剑指OfferII最长连续序列 v = new _119_剑指OfferII最长连续序列();

        System.out.println(v.longestConsecutive(ins));

    }

    // Hash表记录两端数据，也就是可以不用HashMap保存长度
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 记录初始数据对于的长度
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;
        for (int num : nums) {
            if (set.contains(num)) {
                // 查询
                int right = num + 1;
                int rightLen = 0;
                while (set.remove(right)) {
                    right++;
                    rightLen++;
                }
                // 左查询
                // 右查询
                int left = num - 1;
                int leftLen = 0;
                while (set.remove(left)) {
                    left--;
                    leftLen++;
                }
                max = Math.max(max, leftLen + rightLen + 1);
            }
        }
        return max;
    }

    // Hash表记录一端数据
    public int longestConsecutive1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        // 记录初始数据对于的长度
        for (int num : nums) {
            map.put(num, 1);
        }
        int max = 0;
        for (int num : nums) {
            Integer total = map.get(num);
            if (total == null) continue;
            int cur = num;
            // 寻找比他大1元素是否存在Hash表中
            while (map.containsKey(cur + 1)) {
                cur++;
                // 移出
                total += map.remove(cur);
            }
            // 如果是先遍历3, 并且3-9是连续的。如果不写回这个区间的长度话，数据就会错误
            map.put(num, total);
            max = Math.max(max, total);
        }
        return max;
    }

}
